package 开始的剑指offer8月.测试;

import java.util.ArrayList;
// 在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。  [2011-12-31 21:51:27]
public class FindingValue {

        public static void main(String[] args) {
            /**
             * 思路：1. 这样的数只要小于或等于其右侧的最小数就满足右侧条件
             *      2. 大于或等于左侧最大的数就满足左侧条件
             */
            double[] arr = {3, 1, 2, 4, 7, 10, 9, 8};
            double[] arr1 = {1, 6, 9, 2, 1, 5, 15, 20};
            System.out.println(findValue(arr));
            System.out.println();
            System.out.println(findValue(arr1));
            System.out.println();
            System.out.println(findValue(new double[]{-1.1, 3, 7, 79.6, 9.8}));
            System.out.println();
            System.out.println(findValue(new double[]{-5, -2.2, 19, 28, 19, -1.5}));
            System.out.println();
            System.out.println(findValue(new double[]{0, -2.2, 11, 22, 15,-18}));


        }
        // http://blog.jrj.com.cn/1832597331,5284403a.html
        public static ArrayList<Double> findValue(double[] arr) {
            ArrayList<Double> list=new ArrayList<>();
            // 使用一个临时数组来保存 arr 中的每一个数右侧的最小值
            double[] temp = new double[arr.length];
            double min = arr[arr.length - 1];
            for (int j = arr.length - 1; j >= 0; j--) {
                if (arr[j] < min) {
                    min = arr[j];
                }
                temp[j] = min;
            }
            double max = arr[0];
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] > max) {
                    max = arr[i];
                }
                if (arr[i] >= max && arr[i] <= temp[i]) {
                    list.add(arr[i]);
                    //System.out.print(arr[i] + " ");
                }
            }
            return list;
        }
    }


